package hot100;


/*
 * Author：江松
 * Date：2023/4/8 14:02
 *
 任务调度器：
1，推导公式：（自己想的）思路半对，把任务摆放成矩阵（从倒数第二行开始向上摆）
完全能覆盖的情况对的（其实是通用的），不能覆盖的情况考虑错误
应该讨论为
最大次数的个数比周期小或等于：可以摆成长n宽maxn的矩阵
res=t*(maxn-1)+cnt

cnt>t：摆成长n宽maxn的矩阵，此时的CPU待机状态时可以省略的
res=任务数

2，模拟
 */

import java.util.HashMap;
import java.util.Map;

public class Main621 {
    public int leastInterval(char[] tasks, int n) {
        int res=0;
        HashMap<Character,Integer>map=new HashMap<>();
        //最大出现次数,所有字符出现次数
        int maxn=-1;
        int t=n+1;
        for(char c:tasks){
            if(!map.containsKey(c)){
                map.put(c,1);
            }else{
                map.put(c,map.get(c)+1);
            }
            maxn=Math.max(maxn,map.get(c));
        }
        int cnt=0;
        for(char c:map.keySet()){
            if(map.get(c)==maxn){
                cnt++;
            }
        }
        res=t*(maxn-1)+cnt;
        return Math.max(res,tasks.length);
    }

    /*
    public int leastInterval(char[] tasks, int n) {
        int res=0;
        HashMap<Character,Integer>map=new HashMap<>();
        //最大出现次数,所有字符出现次数
        int maxn=-1;
        int sum=0;
        for(char c:tasks){
            if(!map.containsKey(c)){
                map.put(c,1);
            }else{
                map.put(c,map.get(c)+1);
            }
            maxn=Math.max(maxn,map.get(c));
            sum++;
        }
        int other=sum-maxn;
        int t=n+1;
        //说明最大任务无法完全覆盖其他任务
        if(other>maxn*(t-1)){
            res=maxn+other;
        }else{
            int cnt=0;
            for(char c:map.keySet()){
                if(map.get(c)==maxn){
                    cnt++;
                }
            }
            res=t*(maxn-1)+cnt;
        }
        return res;
    }
    */

    public static void main(String[] args) {

    }
}
